package com.ds.bintree.LeetCode;

import java.util.Deque;
import java.util.LinkedList;
/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: 1.我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；
 * 2.我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 index，
 * 并将当前节点作为最后一个弹出的节点的右儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；
 * 3.无论是哪一种情况，我们最后都将当前的节点入栈。
 *
 * @date 2022/9/16 16:18
 */
public class Num105_PreAndInBuildTree2 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = new TreeNode(preorder[0]);
        int inorderindex = 0;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root); //先把根节点入栈

        /**
         * 开始前序遍历逐个往后遍历，判断当前遍历的结点是上一个结点的左子树还是栈里面某个结点的右子树
         */
        for (int i = 1; i <preorder.length ; i++) {
            TreeNode peek = stack.peek();
            int inordervalue = inorder[inorderindex];
            if (inordervalue!=peek.val){
                TreeNode cur = new TreeNode(preorder[i]);
                peek.left = cur;
                stack.push(peek.left);
            }else {
                while(!stack.isEmpty()&& inorder[inorderindex]==stack.peek().val){
                    peek=stack.pop();
                    inorderindex++;
                }
                TreeNode cur = new TreeNode(preorder[i]);
                peek.right = cur;
                stack.push(peek.right);
            }
        }
        return root;
    }
}
